//21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode tmp = null;
        if (list1.val < list2.val) {
            tmp = list1.next;
            list1.next = mergeTwoLists(tmp, list2);
            return list1;
        }
        tmp = list2.next;
        list2.next = mergeTwoLists(list1, tmp);
        return list2;
    }
}
//LCR 170
class Solution {
    public int reversePairs(int[] record) {
        if (record == null || record.length <= 1) {
            return 0;
        }
        int len = record.length;
        return guiBingSort(record, 0, len-1);
    }

    private int guiBingSort(int[] record, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = (l+r) / 2;
        int a = guiBingSort(record, l, mid);
        int b = guiBingSort(record, mid+1, r);
        int c = sort(record, l, mid+1, r);
        return a+b+c;
    }
//按照降序
    private int sort(int[] record, int l, int mid, int r) {
        int a1 = l;
        int a2 = mid;
        int count = 0;
        int[] arr = new int[r-l+1];
        int i = 0;
        while (a1 < mid && a2 <= r) {
            if (record[a1] > record[a2]) {
                count += r-a2+1;
                arr[i++] = record[a1++];
            }
            else {
                while (a2 <= r && record[a1] <= record[a2]) {
                    arr[i++] = record[a2++];
                }
            }
        }
        while (a1 < mid) {
            arr[i++] = record[a1++];
        }
        while (a2 <= r) {
            arr[i++] = record[a2++];
        }
        for (i = 0; i < arr.length; i++) {
            record[l++] = arr[i];
        }
        return count;
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        boolean[] use = new boolean[nums.length];
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        fun(ret, tmp, nums, use, 0, nums.length);
        return ret;
    }

    public void fun(List<List<Integer>> ret, List<Integer> tmp,
        int[] nums, boolean[] use, int size, int len) {
        if (size == len) {
            ret.add(new ArrayList<>(tmp));
        }
        for (int i = 0; i < len; i++) {
            if (use[i]) {
                continue;
            }
            use[i] = true;
            tmp.add(nums[i]);
            fun(ret, tmp, nums, use, size+1, len);
            use[i] = false;
            tmp.remove(size);
        }
    }
}




